use crate::solution::Solution;

impl Solution {
    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
        let (mut jobs, mut max_profit) = ((0..start_time.len()).map(|i| vec![start_time[i], end_time[i], profit[i], profit[i]]).collect::<Vec<_>>(), 0);
        jobs.sort_by(|a, b| a[1].cmp(&b[1]));

        for i in 1..start_time.len() {
            jobs[i][3] = jobs[i][2].max(jobs[i - 1][3]);
            for j in (0..i).rev() {
                if jobs[j][1] <= jobs[i][0] {
                    jobs[i][3] = jobs[i][3].max(jobs[i][2] + jobs[j][3]);
                    break;
                }
            }
            max_profit = max_profit.max(jobs[i][3]);
        }
        max_profit
    }
}
